package LinkedList;

import 数据结构.LinkList.diamond.MyLinkedList;

//设计链表
public class design_linked_list {
    //这里使用单链表
    public static class MyLinkedList {
        //定义节点 单链表使用ListNode
        class ListNode{
            int val;
            ListNode next;
            public ListNode(int val){
                this.val=val;
            }
        }
        //这里去记录虚拟头节点,注意这里并不是第一个元素，这个头结点是空点
        ListNode dummy;
        //记录单链表长度
        int size=0;
        public MyLinkedList() {
            this.size=0;
            //todo：1.这里去给虚拟头节点赋值，不然会导致不能使用dummy.next 因为dummy是null时不能使用.next
            this.dummy=new ListNode(0);
        }
        // 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
        public int get(int index) {
            //先判断是不是超出链表
            //这里因为当链表有一个元素时，链表size=1，而index下标是0，所以index=size时，链表也没有该下标
            if(index>=size) {
                return -1;
            }
            //一般这里是先去获取一个值，避免对虚拟头节点直接进行操作，保护虚拟头结点
            ListNode cur=dummy; //todo:2、这里去copy dummy 而不是next
            //遍历达到index节点
            for (int i = 0; i <=index; i++) {
                cur=cur.next;
            }
            size++;
            return cur.val;
        }
        // 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
        public void addAtHead(int val) {
            ListNode node=new ListNode(val);
            //首先判断链表是否为空
            if(size==0){
                dummy.next=node;
                size++;
                return;
            }
            //非空
            //先记录原先的头结点
            ListNode head=dummy.next;
            dummy.next=node;
            node.next=head;
            size++;
            return;
        }
        // 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
        public void addAtTail(int val) {
            ListNode node=new ListNode(val);
            //首先判断链表是否为空
            if(size==0){
                dummy.next=node;
                size++;
                return;
            }
            //去寻找原先的尾节点
            ListNode cur=dummy;
            while (cur.next!=null){
                cur=cur.next;
            }
            //现在这里的cur就是尾节点
            cur.next=node;
            size++;
            return;
        }
        //将一个值为 val 的节点插入到链表中下标为 index 的节点之前。
        // 如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。
        // 如果 index 比长度更大，该节点将 不会插入 到链表中。
        public void addAtIndex(int index, int val) {
            //如果index=长度
            if(index==size){
                addAtTail(val);
                return;
            }
            if(index>size){
                return;
            }
            //现在下面是正常插入
            ListNode node=new ListNode(val);
            ListNode cur=dummy;
            //这里i是<index，那么循环结束时，就刚好达到下标为index的节点之前的一个节点
            for (int i = 0; i < index; i++) {
                cur=cur.next;
            }
            //原先的下一节点
            ListNode curNext=cur.next;
            cur.next=node;
            node.next=curNext;
            size++;
            return;
        }
        //如果下标有效，则删除链表中下标为 index 的节点。
        public void deleteAtIndex(int index) {
            if(index<0||index>=size){
                return;
            }
            ListNode cur=dummy;

            //找到下标为index-1的节点 即index是他的下一节点
            for (int i = 0; i < index; i++) {
                cur=cur.next;
            }
            ListNode indexNext=cur.next.next;
            cur.next=indexNext;
            size--;
            return;
        }

    }
    //这里使用双链表
    public static class MyLinkedList_double{
        //节点的定义[与单链表比多了一个前驱节点，单链表只有后继next节点]
        class ListNode{
            int val;
            // 这里展示不同 这里展示前驱节点 后继节点
            ListNode pre,next;
            public ListNode(int val){
                this.val=val;
                this.pre=null;
                this.next=null;
            }
        }
        //虚拟头节点
        ListNode dummyHead;
        //虚拟尾节点
        ListNode dummyTail;
        //todo:定义虚拟头尾节点的用处
        int size;
        //链表的空参构造
        public MyLinkedList_double(){
            this.size=0;
            this.dummyHead=new ListNode(0);
            this.dummyTail=new ListNode(0);
            this.dummyHead.next=dummyTail;
            this.dummyTail.pre=dummyHead;
        }
        // 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
        public int get(int index) {
            if(index>=size){
                return -1;
            }
            ListNode cur=dummyHead;
            //这里最终得到的是下标为index的节点
            for (int i = 0; i <=index; i++) {
                cur=cur.next;
            }
            return cur.val;
        }
        // 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
        public void addAtHead(int val) {
            ListNode node=new ListNode(val);
            //原先的头节点
            ListNode head=dummyHead.next;
            dummyHead.next=node;
            node.pre=dummyHead;
            node.next=head;
            head.pre=node;
            size++;
        }
        // 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
        public void addAtTail(int val) {
            ListNode node=new ListNode(val);
            //原来的尾节点
            ListNode tail=dummyTail.pre;
            tail.next=node;
            node.pre=tail;
            node.next=dummyTail;
            dummyHead.pre=node;
            size++;

        }
        //将一个值为 val 的节点插入到链表中下标为 index 的节点之前。
        // 如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。
        // 如果 index 比长度更大，该节点将 不会插入 到链表中。
        public void addAtIndex(int index, int val) {
            ListNode node=new ListNode(val);
            if(size==index){
                addAtTail(val);
                return;
            }
            if(index>size){
                return;
            }
            ListNode cur=dummyHead;
            //todo：这里最终得到的是下标为index的节点
            for (int i = 0; i <= index; i++) {
                cur=cur.next;
            }
            //得到原先的index的前驱节点
            ListNode oldPre=cur.pre;
            oldPre.next=node;
            cur.pre=node;
            node.pre=oldPre;
            node.next=cur;
            size++;
        }
        //如果下标有效，则删除链表中下标为 index 的节点。
        public void deleteAtIndex(int index) {
            if(index<0||index>=size){
                return;
            }
            ListNode cur=dummyHead;
            for (int i = 0; i <= index; i++) {
                cur=cur.next;
            }
            cur.pre.next=cur.next;
            cur.next.pre=cur.pre;
            size--;
        }

    }


    public static void main(String[] args) {
          MyLinkedList obj = new MyLinkedList();
             int param_1 = obj.get(0);
             obj.addAtHead(1);
             obj.addAtTail(3);
             obj.addAtIndex(1,2);
             obj.deleteAtIndex(1);
    }
}
